package cn.zhaoyuening.algorithms.dynamic;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

/**
 * Created by Buynow on 2017/8/14.
 */
public class ExchangeMoneyMin {
    public static void helper(int[] moneyArr,int aim) {
        int[][] dp = new int[moneyArr.length][aim + 1];
        int max = Integer.MAX_VALUE;
        for (int i=1;i<=aim;i++) {
            if (i % moneyArr[0] == 0) {
                dp[0][i] = i / moneyArr[0];
            }else{
                dp[0][i] = max;
            }
        }
        for (int i=0;i<moneyArr.length;i++) {
            dp[i][0] = 0;
        }
        int curMoney = 0;
        int tmpCount = 0;
        int tmpAim = 0;
        for (int i=1;i<moneyArr.length;i++) {
            curMoney = moneyArr[i];
            for (int j=1;j<dp[0].length;j++) {
                tmpAim = j;
                tmpCount = max;
                for (int k=1;j-k*curMoney>=0;k++) {
                    if (dp[i][tmpAim - k * curMoney] != max) {
                        tmpCount = Math.min(tmpCount, dp[i][tmpAim - k * curMoney] + k);
                    }
                }
                tmpCount = Math.min(tmpCount, dp[i - 1][tmpAim]);
                dp[i][j] = tmpCount;
            }
        }

        System.out.println(dp[moneyArr.length - 1][aim]);
    }

    public static void helper2(int[] moneyArr,int aim) {
        int[][] dp = new int[moneyArr.length][aim + 1];
        int max = Integer.MAX_VALUE;
        for (int i=1;i<=aim;i++) {
            if (moneyArr[0] == i) {
                dp[0][i] = 1;
            }else {
                dp[0][i] = max;
            }
        }
        for (int i=0;i<moneyArr.length;i++) {
            dp[i][0] = 0;
        }
        int curMoney = 0;
        int tmpCount = max;
        for (int i=1;i<moneyArr.length;i++) {
            curMoney = moneyArr[i];
            for (int j=1;j<=aim;j++) {
                tmpCount = max;
                if (j >= curMoney) {
                    if (dp[i-1][j - curMoney] != max) {
                        tmpCount = dp[i-1][j-curMoney]+1;
                    }
                }
                tmpCount = Math.min(tmpCount, dp[i - 1][j]);
                dp[i][j] = tmpCount;
            }
        }
        System.out.println(dp[moneyArr.length-1][aim]);
    }

    public static void helper3(int[] moneyArr,int aim){
        int[][] dp = new int[moneyArr.length][aim + 1];
        for (int i=0;i<moneyArr.length;i++) {
            dp[i][0] = 1;
        }

        for (int i=1;i<=aim;i++) {
            if (i % moneyArr[0] == 0) {
                dp[0][i] = 1;
            }else {
                dp[0][i] = 0;
            }
        }

        int tmpCount = 0;
        int tmpMoney = 0;

        for (int i=1;i<dp.length;i++) {
            tmpMoney = moneyArr[i];
            for (int j=1;j<=aim;j++) {
                tmpCount = 0;
                for (int k = 1; j >= k * tmpMoney; k++) {
                    tmpCount += dp[i - 1][j - k * tmpMoney];
                }
                tmpCount += dp[i - 1][j];
                dp[i][j] = tmpCount;
            }
        }

        System.out.println(dp[moneyArr.length-1][aim]);



    }

    public static void main(String[] args) {
//        helper2(new int[]{5,2,5,3},15);
        helper3(new int[]{5,10,25,1},15);
    }
}
